Feedback vertex set について

Words near each other

Dictionary Lists

mini英和辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

Cycle Cutset ：ウィキペディア英語版

Feedback vertex set
In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph.
The feedback vertex set problem is an NP-complete problem in computational complexity theory. It was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.
== Definition ==

The decision problem is as follows:
:INSTANCE: An (undirected or directed) graph

G = (V, E)

and a positive integer

k

.
:QUESTION: Is there a subset

X \subseteq V

with

|X| \leq k

such that

G

with the vertices from

X

deleted is cycle-free?
The graph

G(\setminus X)

that remains after removing

X

from

G

is an induced forest (resp. an induced directed acyclic graph in the case of directed graphs). Thus, finding a minimum feedback vertex set in a graph is equivalent to finding a maximum induced forest (resp. maximum induced directed acyclic graph in the case of directed graphs).

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「Feedback vertex set」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース